#include <unordered_set>
#include <ctime>
#include "IGraph.h"
#include "Algo.h"
#include "MakeGraph.h"

const int ALGO_TESTS_NUMBER = INT_MAX / (1024 * 1024 * 4);


class FirstSearchTester {
public:

    void StartProcessingVertex(int vertex) {
	if (vertices_processed_.find(vertex) != vertices_processed_.end()) throw std::logic_error("FAIL");
        vertices_processed_.insert(vertex);
    }

    void ProcessingEdge(int vertex, int incident_vertex) {
        edges_processed_.insert(Edge(vertex, incident_vertex));
    }

    void LeaveVertex(int vertex) {}

    std::set<int> GetVerticesProcessed() { return  vertices_processed_;}

    std::set<Edge> GetEdgesProcessed() { return edges_processed_;}

private:
    std::set<int> vertices_processed_;
    std::set<Edge> edges_processed_;
};


inline void OneFirstSearchTest(const std::vector<Edge> &list_of_edges, int vertices_amount, FirstSearchTester& tester) {
    std::set<int> vertices_set;
    for (int vertex = 0; vertex < vertices_amount; ++vertex) vertices_set.insert(vertex);

    if (tester.GetVerticesProcessed() != vertices_set) throw std::logic_error("FAIL");

    std::set<Edge> set_of_edges(list_of_edges.begin(), list_of_edges.end());
    if (tester.GetEdgesProcessed() != set_of_edges) throw std::logic_error("FAIL");
}


inline void FirstSearchTests(const std::vector<Edge> &list_of_edges, int vertices_amount) {
        auto graph = MakeCompactGraph(list_of_edges, vertices_amount);

    try {
        FirstSearchTester dfs_tester;
        DFS(*graph, dfs_tester);
        OneFirstSearchTest(list_of_edges, vertices_amount, dfs_tester);
    } catch (const std::exception& ex) {
        throw std::logic_error("TestDFS: " + std::string(ex.what()));
    }

    try {
        FirstSearchTester bfs_tester;
        DFS(*graph, bfs_tester);
        OneFirstSearchTest(list_of_edges, vertices_amount, bfs_tester);
    } catch (const std::exception& ex) {
         throw std::logic_error("TestBFS: " + std::string(ex.what()));
    }
}


inline void FindSircle(const std::vector<Edge>& list_of_edges, int vertex, std::vector<state>& processed, 
			   bool &is_sircle) {

    processed[vertex] = IN_PROCESSING;

    for (int edge_index = 0; edge_index < list_of_edges.size(); ++edge_index) {
	if (list_of_edges[edge_index].begin_ != vertex) continue;

	if (processed[list_of_edges[edge_index].end_] == IN_PROCESSING) { 
	    is_sircle = true;
	    return;
	}

	if (processed[list_of_edges[edge_index].end_] == NOT_PROCESSED) { 
	    FindSircle(list_of_edges, list_of_edges[edge_index].end_, processed, is_sircle); 
	    if (is_sircle) return;
	}
    }
    processed[vertex] = PROCESSED;
}

inline bool IsSircle(int vertices_amount, const std::vector<Edge>& list_of_edges) {
    std::vector<state> processed(vertices_amount, NOT_PROCESSED);
    bool is_sircle = false;

    for (int vertex = 0; vertex < vertices_amount; ++vertex) {
	if (!processed[vertex]) {
	    FindSircle(list_of_edges, vertex, processed, is_sircle);
	    if (is_sircle) return true;
	}
    }

    return false;
}


inline void TestTopologicalSort(const std::vector<Edge> &list_of_edges, int vertices_amount) {

    try {
        auto graph = MakeCompactGraph(list_of_edges, vertices_amount);
 
        if (IsSircle(vertices_amount, list_of_edges)) return;

        TopologicalSort topological_sort(vertices_amount);
        DFS(*graph, topological_sort);

        std::vector<int> topologically_ordered_vertices = topological_sort.GetTopologicalOrder();
        if (topologically_ordered_vertices.size() != vertices_amount) throw std::logic_error("FAIL");

        for (int i = 0; i < topologically_ordered_vertices.size() - 1; ++i) {
            for (int j = i + 1; j < topologically_ordered_vertices.size(); ++j) {
                if (graph->HasEdge(topologically_ordered_vertices[j], topologically_ordered_vertices[i]))
                     throw std::logic_error("FAIL");
            }
        } 
    } catch (const std::exception& ex) {
        throw std::logic_error("TestTopologicalSort: " + std::string(ex.what()));
    }
}

class AllSmallListOfEdgesGenerator {
public:

    AllSmallListOfEdgesGenerator(int vertices_amount) : vertices_amount_(vertices_amount), next_list_of_edges_number_(0) {}

    std::vector<Edge> NextSmallListOfEdges() {
        try {

	    if (next_list_of_edges_number_ >= (1 << (vertices_amount_ * vertices_amount_)) )
		throw std::logic_error("FAIL in generating graph");

            std::vector<Edge> next_list_of_edges;

	    for (int i = 0; i < vertices_amount_ * vertices_amount_; ++i) {
	        if ((next_list_of_edges_number_ & (1 << i)) != 0) 
	       	    next_list_of_edges.push_back(Edge(i / vertices_amount_, i % vertices_amount_));
	    }

	    next_list_of_edges_number_++;

	    return next_list_of_edges;       
        } catch (const std::exception& ex) {
            throw std::logic_error(std::string(ex.what()));
        }
    }

private:
    int vertices_amount_;
    int next_list_of_edges_number_;
};



// tests of TopologicalSort on all small graphs with vertices amount <= 4
inline void TestAlgoOnSmallGraphs() {
    try {
        for (int vertices_amount = 1; vertices_amount < 5; ++vertices_amount) {
	    AllSmallListOfEdgesGenerator small_list_of_edges_generator(vertices_amount);

            for (int list_of_edges_number = 0; list_of_edges_number < 
			(1 << (vertices_amount * vertices_amount)); ++list_of_edges_number) {

		std::vector<Edge> next_list_of_edges = small_list_of_edges_generator.NextSmallListOfEdges();
		
		FirstSearchTests(next_list_of_edges, vertices_amount);
		TestTopologicalSort(next_list_of_edges, vertices_amount);
 	    } 

        }
    } catch (const std::exception& ex) {
        throw std::logic_error("TestAlgoOnSmallGraphs: " + std::string(ex.what()));
    }
}





void TestAlgo() {
    std::cout<<"TestAlgoOnSmallGraphs : \n";
    TestAlgoOnSmallGraphs();
    std::cout<<"OK\n";

    std::cout<<"TestsTopologicalSort (Asyclic graphs) : \n";
    for (int i = 0; i < ALGO_TESTS_NUMBER; ++i) {
	std::pair<std::vector<Edge>, int> new_alyclic_graph = CreateRandomAsyclicListOfEdges();
	std::vector<Edge> list_of_edges = new_alyclic_graph.first;
	int vertices_amount = new_alyclic_graph.second;

        TestTopologicalSort(list_of_edges, vertices_amount);
    }
    std::cout<<"OK\n";

    std::cout<<"TestsAlgo on random graphs : \n";
    for (int i = 0; i < ALGO_TESTS_NUMBER; ++i) {
	std::pair<std::vector<Edge>, int> new_graph = CreateRandomListOfEdges();
	std::vector<Edge> list_of_edges = new_graph.first;
	int vertices_amount = new_graph.second;

	std::cout<<"TestDFS : \n";
        FirstSearchTests(list_of_edges, vertices_amount);
	std::cout<<"OK\n";

	std::cout<<"TestTopologicalSort : \n";
	TestTopologicalSort(list_of_edges, vertices_amount);
	std::cout<<"OK\n";
    }

}

